package com.summli.basic.class08;

import java.util.ArrayList;

/**
 * 给定一棵二叉树的头节点head，
 * * 返回这颗二叉树中最大的二叉搜索子树的大小
 * 二叉搜索树：左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
 * info:是否是二叉树，当前树的大小，min,max
 */
public class Code04_MaxSubBSTSize {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class Info {
        public boolean isBST;
        public int size;
        public int max;
        public int min;

        public Info(boolean isBST, int size, int max, int min) {
            this.isBST = isBST;
            this.size = size;
            this.max = max;
            this.min = min;
        }
    }


    // 第二种方法:递归二叉数的套路
    public static int maxSubBSTSize2(Node head) {
        if (head == null) {
            return 0;
        }
        return process(head).size;
    }

    private static Info process(Node head) {
        if (head == null) {
            return null;
        }
        Info lefInfo = process(head.left);
        Info rightInfo = process(head.right);
        int min = head.value;
        int max = head.value;
        int size = 0;//默认当前层不是搜索二叉树
        boolean isBST = false;
        if (lefInfo != null) {
            min = Math.min(min, lefInfo.min);
            max = Math.max(max, lefInfo.max);
            size = Math.max(size, lefInfo.size);
        }
        if (rightInfo != null) {
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
            size = Math.max(size, rightInfo.size);
        }
        if ((lefInfo == null ? true : (lefInfo.isBST && lefInfo.max < head.value))
                && (rightInfo == null ? true : (rightInfo.isBST && rightInfo.min > head.value))) {
            isBST = true;
            size = (lefInfo == null ? 0 : lefInfo.size) + (rightInfo == null ? 0 : rightInfo.size) + 1;
        }
        return new Info(isBST, size, max, min);
    }

    // 第一种方法：中序遍历
    public static int maxSubBSTSize1(Node head) {
        if (head == null) {
            return 0;
        }
        int h = getBSTSize(head);
        if (h != 0) {
            return h;
        }
        return Math.max(maxSubBSTSize1(head.left), maxSubBSTSize1(head.right));
    }

    public static int getBSTSize(Node head) {
        if (head == null) {
            return 0;
        }
        ArrayList<Node> arr = new ArrayList<>();
        middle(head, arr);
        // 遍历arr
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i - 1).value >= arr.get(i).value) {
                return 0;
            }
        }
        return arr.size();
    }

    // 中序遍历
    private static void middle(Node cur, ArrayList<Node> arr) {
        if (cur == null) {
            return;
        }
        middle(cur.left, arr);
        arr.add(cur);
        middle(cur.right, arr);
    }


    //=====================
    // for test
    // for test
    public static Node generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static Node generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    public static void main(String[] args) {
        int maxLevel = 4;
        int maxValue = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
            if (maxSubBSTSize1(head) != maxSubBSTSize2(head)) {
                System.out.println("Oops!");
                break;
            }
        }
        System.out.println("finish!");
    }

}

